package code;

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Sort {





















    /**
     * 快速排序
     * @param array
     * @return
     */
    public static int[] quickSort(int[] array) {
        int len;
        if(array == null
                || (len = array.length) == 0
                || len == 1) {
            return array;
        }
        sort(array, 0, len - 1);
        return array;
    }

    /**
     * 快排核心算法，递归实现
     * @param array
     * @param left
     * @param right
     */
    public static void sort(int[] array, int left, int right) {

        if(left > right) {
            return;
        }
        int base = array[left];
        int i = left;
        int j = right;
        while (i != j){
            //从右往左找，找到小于base的就停止，否则j--
            while(array[j] >= base && i < j){
                j--;
            }
            //从左往右，大于base就停止，否则i++
            while (array[i] <= base && i < j){
                i++;
            }
            //一轮结束后把符合条件的替换位置
            if(i < j){
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //全部执行结束后把base和中间值换位置
        array[left] = array[i];
        array[i] = base;
        //递归
        sort(array,left, i - 1);
        sort(array, i + 1, right);



    }

    //maopao 小到大
    public static int[] maopaoSort(int[] ints){
        int temp = 0;
        for(int i = 0; i < ints.length - 1; i++){
            for (int j = i + 1; j < ints.length; j++){
                if (ints[i] > ints[j]){
                     temp = ints[j];
                     ints[j] = ints[i];
                    ints[i] = temp;

                }
            }
        }
        return ints;
    }



}
